/**
 * 给定一个 没有重复 数字的序列，返回其所有可能的全排列。
 * 输入: [1,2,3]
 输出:
 [
 [1,2,3],
 [1,3,2],
 [2,1,3],
 [2,3,1],
 [3,1,2],
 [3,2,1]
 ]

 回溯公式:
 result = []
 def backtrack(路径, 选择列表):
 if 满足结束条件:
 result.add(路径)
 return

 for 选择 in 选择列表:
 做选择
 backtrack(路径, 选择列表)
 撤销选择
 */

const arr = [1, 2, 3]
function permute(arr) {
    let res = []
    DFS([])

    function DFS(num) {
        // 如果到达叶子节点了， 直接存进去
        if (num.length === arr.length) {
            res.push([...num])
            return
        }
        // 如果没有达到叶子
        for (let i = 0; i < arr.length; i++) {
            if (num.includes(arr[i])) {
                // 跳出本次循环
                continue;
            }
            num.push(arr[i])
            DFS(num)
            // 达到叶子，弹出最外面一个，向上回溯一下
            num.pop()
        }
    }

    return res
}

// console.log(permute(arr));




function allSort(arr) {
    let res= []
    function DFS(path){
        if(path.length === arr.length){
             res.push([...path])
            return;
        }
        for(let i=0; i<arr.length; i++) {
            if(path.includes(arr[i])){
                continue;
            }
            path.push(arr[i])
            DFS(path)
            path.pop()
        }
    }
    DFS([])
    return res;
}

console.log(allSort(arr));


